In recent years, computerized navigation and route guidance systems have come into common use among consumers as well as transportation professionals to assist drivers and pedestrians in navigating a network to reach their destination. Such systems are also currently being adapted to guide autonomous robots and robotized vehicles. If a person or robot is delayed along a planned route or deviates from a planned route either inadvertently (such as by becoming stuck in unexpected traffic, by making a wrong turn, or by being directed by police to make a detour) or intentionally (to seek fuel or food, or to go around stalled traffic), there is a need to detect this situation and recalculate a new route to continue on to the destination. A computerized navigation system will typically do so by calculating a new best route to the destination, ignoring the previously planned route, or it may calculate a best route back to the previously planned route, or, such as in the case of changing traffic conditions, it may calculate alternative routes that incorporate the latest real-time traffic information. The system may provide one route by default, or it may propose alternatives for the person navigating to choose from. Such systems are suitable for situations in which a driver or pedestrian is ultimately responsible for and has a large degree of control over the decision-making as to which route to take, and strict adherence to a prescribed route is not required.
In other situations, it is not allowable or desirable for a driver or pedestrian, or feasible for a robot, to be completely responsible for route decision-making. For example, it may not be allowable for dangerous, oversize or overweight cargo to move other than on a prescribed route, or for a parolee to deviate from a set route to and from work, or it may not be desirable to let a person of limited experience or faculties be responsible for route decision-making, or it may be desirable from an efficiency or quality standpoint to give a driver or pedestrian expert guidance as to which route to take. In these situations, the driver or pedestrian's navigation system must typically receive initial routing instructions from a controlling authority, such as a dispatcher or supervisor, and then, if they go out-of-route or fall behind schedule, contact that controlling authority, report where they are out-of-route, and await new instructions. This process of contacting and waiting for new instructions may be infeasible if there is a gap in communications coverage, or it may be time-consuming and inefficient if the controlling authority only works certain shifts or has a lengthy work queue, or it may be uneconomic.
In circumstances where a controlling authority has at least partial responsibility for routing decisions, it is often desirable from an efficiency perspective to pre-authorize the driver or pedestrian to make certain deviations from and return to a prescribed route on their own authority, such as to stop for a short time at an interstate exit for food or fuel and return to the interstate at that same exit. But in certain cases, such as the shipment of munitions, even short deviations, or stopping for a short time along a prescribed route without deviating, may be undesirable due to security concerns. Different cases may also apply to how the driver or vehicle needs to react if they stop for a longer time or make a longer deviation off-route, ranging from the pleasure traveler who is free to stop or drive anywhere on a whim, to the transporter of an oversize or overweight load who must strictly follow a prescribed route at a particular time that has been pre-cleared to handle a vehicle of their size and weight.
U.S. Pat. Nos. 5,068,656 and 6,839,627 describe systems and methods for detecting out-of-route events for trucks and reporting these to a central dispatcher. U.S. Pat. No. 6,718,235 describes a method and apparatus for determining that a vehicle has deviated from a planned route in excess of a predetermined limit and shutting down the vehicle unless or until a central authority authorizes otherwise. U.S. Pat. No. 7,385,500 describes a system and method for detecting events for mobile assets and reporting these to a variety of interested parties. These systems, methods and apparatus detect and report in a “black box” fashion, without provision to provide any navigation or route guidance.
U.S. Pat. No. 5,262,775 describes a navigation system that detects deviations from a calculated route, alerts the driver, and allows the driver to request computation of a new route. U.S. Pat. No. 5,689,423 describes a system for computing return routes to a planned route for each potential deviation from the planned route, and warning the driver in advance of each potential deviation whose incremental return route cost exceeds a threshold. U.S. Pat. No. 7,024,287 describes an autopilot system that, following a manual deviation from an original route, automatically chooses which waypoint along the original route to return to. U.S. Pat. No. 7,945,386 describes a device and method for detecting that a vehicle has deviated from an original route, determining reroutes to one or more intermediate points along the original route, and selecting a reroute based on cost. U.S. application 2008/0275636 describes an apparatus and method for determining that a vehicle has deviated from a planned route, and if so, determining if it deviated before a planned intermediate point, and if so, determining whether to continue to route via the intermediate point, and if so calculating a new route to the final destination via the intermediate point, otherwise calculating a route direct to the destination. U.S. application 2011/0213548 describes a navigation system that determines whether to recalculate a route depending on a tolerance of deviation from the original route. These systems, device and method are completely autonomous and do not receive any instructions from or send any information to a controlling authority.
U.S. Pat. Nos. 6,052,645, 6,107,944, 6,892,133,7,149,625 and 7,406,381, and U.S. application Ser. No. 2005/0043884 describe methods, systems and apparatus for client/server and distributed navigation systems. While the computing power of these systems is distributed, the authority and control over route choice is not distributed.
U.S. Pat. No. 5,878,368 describes a navigation system with user definable cost values, including the ability for a user to designate particular road segments to avoid or favor. However, the authority to make such a designation rests entirely with the end user in the vehicle, it is not distributed.
International application publication WO2010/111833 A1 describes a method and program for displaying points of interest that can be reached from a planned route within a threshold cost, and can return to the planned route within a second threshold cost, and the sum of the two costs is less than a third threshold cost. This method and program do not determine whether a vehicle actually deviates from a planned route, and does not incorporate selecting among varying criteria of strictness for detecting such a deviation or for returning to the planned route.
In a presentation by the inventors titled “ALK Map Data and Development Roadmap” presented May 5, 2011 at the ALK Technology Summit, slides 26-28 refer to the general concept of a dispatching system sending a prescribed route to a navigation system, and the navigation system thereafter following the prescribed route as a preference versus a requirement versus how strongly to follow the route.